﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.BacktrackingCode
{
    class PartitionCode
    {
        List<IList<string>> result;
        List<string> path;
        //===========================================力扣131 分割回文串
        //给你一个字符串s，请你将s分割成一些子串，是每个子串都是回文串。返回s所有可能的分割方案
        //回文串：正读反读都一样的字符串
        public IList<IList<string>> Partition(string s)
        {
            result = new List<IList<string>>();
            path = new List<string>();
            BackTracking(s, 0);
            return result;
        }
        void BackTracking(string s, int startIndex)
        {
            if (startIndex >= s.Length)
            {
                result.Add(new List<string>(path));
                return;
            }

            for (int i = startIndex; i < s.Length; i++)
            {
                if (IsPalindrpme(s, startIndex, i))
                {//是回文串
                    string str = s.Substring(startIndex, i - startIndex + 1);//获取[startIndex,i]在s中的子串
                    path.Add(str);
                }
                else
                    continue;

                BackTracking(s, i + 1);//寻找以i+1为起始位置的子串
                path.RemoveAt(path.Count - 1);
            }
        }
        bool IsPalindrpme(string s, int start, int end)
        {//判断是否是回文子串，双指针法
            for (int i = start, j = end; i < j; i++, j--)
            {
                if (s[i] != s[j])
                    return false;
            }
            return true;
        }

        //=====================================================力扣93 复原IP地址
        //给定一个只包含数字的字符串，用以表示一个IP地址，返回所有可能从s获得的有效ip地址。可以按任何顺序返回答案
        //有效ip地址：正好由四个整数（每个整数位于0-255之间，且不能还有前导0），整数之前用.分割。
        //例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
        public IList<string> RestoreIpAddResses(string s)
        {
            path = new List<string>();
            BackTracking_2(s, 0, 0);
            return path;
        }
        void BackTracking_2(string s, int startIndex, int pointNum)
        {
            if (pointNum == 3)
            {//逗点数量为3时 分割结束
                if (IsValid(s, startIndex, s.Length - 1))
                    path.Add(string.Copy(s));
                return;
            }

            for (int i = startIndex; i < s.Length; i++)
            {
                if (IsValid(s, startIndex, i))//判断是否合法
                {
                    s = s.Insert(i + 1, ".");//插入逗点
                    pointNum++;
                    BackTracking_2(s, i + 2, pointNum);//插入逗点之后下一个子串的起始位置为i+2
                    pointNum--;//回溯
                    s = s.Remove(i + 1, 1);//回溯删除逗点
                }
                else
                    continue;//不合法
            }
        }
        bool IsValid(string s, int start, int end)
        {
            if (start > end)
                return false;

            if (s[start] == '0' && start != end)
                return false;//0开头的数字不合法
            int num = 0;
            for (int i = start; i <= end; i++)
            {
                if (s[i] > '9' || s[i] < '0')
                    return false;//非数字不合法
                num = num * 10 + (s[i] - '0');
                if (num > 255)//大于255 不合法
                    return false;
            }
            return true;
        }

    }
}
